package org.skywork.top.core.algorithm.str;

import java.util.HashMap;
import java.util.Map;

/**
 * 最长回文子串
 */
public class no_5 {

    /**
     * 给你一个字符串 s，找到 s 中最长的 回文 子串。
     */

    public boolean isPalindromic(String s) {
        int len = s.length();
        for (int i = 0; i < len / 2; i++) {
            if (s.charAt(i) != s.charAt(len - i - 1)) {
                return false;
            }
        }
        return true;
    }


    public String longestPalindrome(String s) {

        /**
         * 示例 1：
         *
         * 输入：s = "babad"
         * 输出："bab"
         * 解释："aba" 同样是符合题意的答案。
         *
         *
         * 示例 2：
         *
         * 输入：s = "cbbd"
         * 输出："bb"
         *
         */

        /**
         * 1. 需要双指针遍历整个字符串
         * 2.
         */
        int len = s.length();
        Map<Character, Integer> map = new HashMap<>();
        for(int start = 0, end = 0; end < len; end++){
            char c = s.charAt(end);
            if(map.containsKey(c)){
                start = Math.max(map.get(c), start);
            }
            map.put(c, end + 1);
        }
        return null;
    }


    public String preProcess(String s) {
        int n = s.length();
        if (n == 0) {
            return "^$";
        }
        String ret = "^";
        for (int i = 0; i < n; i++)
            ret += "#" + s.charAt(i);
        ret += "#$";
        return ret;
    }

    // 马拉车算法
    public String longestPalindrome2(String s) {
        String T = preProcess(s);
        int n = T.length();
        int[] P = new int[n];
        int C = 0, R = 0;
        for (int i = 1; i < n - 1; i++) {
            int i_mirror = 2 * C - i;
            if (R > i) {
                P[i] = Math.min(R - i, P[i_mirror]);// 防止超出 R
            } else {
                P[i] = 0;// 等于 R 的情况
            }

            // 碰到之前讲的三种情况时候，需要利用中心扩展法
            while (T.charAt(i + 1 + P[i]) == T.charAt(i - 1 - P[i])) {
                P[i]++;
            }

            // 判断是否需要更新 R
            if (i + P[i] > R) {
                C = i;
                R = i + P[i];
            }

        }

        // 找出 P 的最大值
        int maxLen = 0;
        int centerIndex = 0;
        for (int i = 1; i < n - 1; i++) {
            if (P[i] > maxLen) {
                maxLen = P[i];
                centerIndex = i;
            }
        }
        int start = (centerIndex - maxLen) / 2; //最开始讲的求原字符串下标
        return s.substring(start, start + maxLen);
    }
}
